% WARNING: matlab is crappy and forced me to put functions inside functions
% instead of having proper code structure with actual constants, arguments
% and whatnot...

function stuff
    t = cputime;
    
    function work( test )
        % loads the trace file before using it (multiple times)
        % trace file contains the exact execution trace of the simulation
        trace = strcat('results/results.conditional_trace.',test,'.csv');
        assert( exist(trace,'file') ~=0 );
        file = importdata(trace, '\t', 1);
        data = file.data;

        fprintf('\n[ %s ]\n',trace);
        printer = classify( file );


        fprintf('-------- WRONGS GSHARE --------\n');
        classifyWrongs('gshare_base');
        fprintf('-------- WRONGS GS NOCOL --------\n');
        classifyWrongs('gshare_nocol');
        fprintf('-------- WRONGS GS UNL --------\n');
        classifyWrongs('gshare_unlimited');
        fprintf('-------- WRONGS GS PATH --------\n');
        classifyWrongs('gshare_path');
      
        fprintf('-------- WRONGS LCL  --------\n');
        classifyWrongs('local_limited');
        fprintf('-------- WRONGS LCL NOCOL  --------\n');
        classifyWrongs('local_nocol');
        fprintf('-------- WRONGS LCL UNL  --------\n');
        classifyWrongs('local_unlimited');
        fprintf('-------- WRONGS TAGE  --------\n');
        classifyWrongs('ISL_TAGE-cond');
        
        % TODO: add others here...
        
        function classifyWrongs( predictor )
            PRED_COLUMN = getIndex(file.textdata, predictor );
            REAL_COLUMN = getIndex(file.textdata,'real');
            assert( PRED_COLUMN ~= -1 );
            assert( REAL_COLUMN ~= -1 );
            printer( data( data(:,PRED_COLUMN) ~= data(:,REAL_COLUMN) , : ) );
        end
    
        fprintf('-------- CLUSTERS GSHARE --------\n');
        clusters( file , 'gshare_base' );
        
        
        fprintf('-------- CORRELATION LOCAL --------\n');
        %correlationGSAHRE( file , 30000, 31000, printer);
        correlationLOCAL( file , 30000, 40000, printer);
        
    end

    
    
    work('CLIENT04');
    work('INT04');
    work('MM01');
    work('SERVER03');
    work('WS04');
    

    fprintf('done. %.2fs\n', cputime-t );
end

function clusters( file , predictor )

    REAL_COLUMN = getIndex(file.textdata,'real');
    PRED_COLUMN = getIndex(file.textdata, predictor );
    
    assert( REAL_COLUMN ~= -1 );
    assert( PRED_COLUMN ~= -1 );
    
    trace = file.data;
    
    wrong = xor( trace(:,REAL_COLUMN) , trace(:,PRED_COLUMN) );
    
    c=0;
    chunks = 0;
    accum = zeros(11,1);
    avg = 0;
    total = 0;
    filter_point = 2;
    
    for i=1:size(wrong,1)
        if( wrong(i,1) == 1 )
            % found possible wrong chunk, start counting
            c = c + 1;
        else
            % now the predictor is correct ( reset c )
            if( c > 0 )
                % if it was bigger than 0, then count this as a new chunk
                chunks = chunks+1;
                
                %%%% hypothetical predictor %%%
                
                if( c >= filter_point ) % invert prediction after more than 1 missed
                    if( c > 10 )
                        accum(11,1) = accum(11,1) + 1;
                    else
                        accum(c,1) = accum(c,1) + 1;
                    end
                    avg = avg + c;
                    total = total+1;
                end
            end
            c = 0;
        end
    end
    
    % --- Output Print --- %
    
    fprintf('--- clusters ---\n');
    for i=2:size(accum,1)
        if( i > 10 )
            fprintf('10+\t%d\t%.2f\n', accum(i,1),accum(i,1)/total);
        else
            fprintf('%d\t%d\t%.2f\n', i,accum(i,1),accum(i,1)/total);
        end
    end
    fprintf('average:\t%.2f\n',avg/total);
    
    fprintf('--- predictors ( after %d wrongs )---\n',filter_point );
    
    predictions = size( trace, 1 );
    wrongs = size(trace( trace(:,REAL_COLUMN) ~= trace(:,PRED_COLUMN), : ),1);
    
    baseline = wrongs;
    % if switches back at the exactly correct time
    optimal = wrongs-avg+(total*filter_point);
    % if switches back after missing one (thus, add total as missed)
    worst = wrongs-avg+total+(total*filter_point);
    
    fprintf('BASE : %3.2f \t ( %5d / %d ) \n', baseline/predictions*100 , baseline, predictions );
    fprintf('BEST : %3.2f \t [ %5d | %3.2f ] \n', optimal/predictions*100 , (optimal-baseline), (optimal-baseline)/predictions*100  );
    fprintf('WORST: %3.2f \t [ %5d | %3.2f ] \n', worst/predictions*100 , (worst-baseline),  (worst-baseline)/predictions*100 );

end

function correlationLOCAL( file , MIN , MAX , printer )
    data = file.data;

    HISTORY_LENGTH = 32; % 32-bit history
    LOCAL_SIZE = 18; % both HISTORY_TABLE and COUNTER_TABLE

    % number of lines is dimension 1
    MAX = min( size(data,1) , MAX );
    MIN = min( MIN, MAX );
    MIN = max( 1 , MIN );
    
    data = data(MIN:MAX,:); % trim data
    
    % each prediction is marked with a set ID
    
    
    function [c MAP ID] = addOrSet( i, MAP , uid , ID , counter )
        c = counter;
        if( isKey( MAP ,uid) )
            ID(i,1) = MAP(uid);
        else
            c = c + 1;
            ID(i,1) = c; % prediction 'i' has mark 'c'
            MAP(uid) = c; % key has mark 'c'
        end
    end

    % LL local_limited
    LL_ID = zeros(size(data,1),1);
    LL_counter = 0;
    LL_map = containers.Map();
    LL_hist = containers.Map();
    
    % LN local_nocol
    LN_ID = zeros(size(data,1),1);
    LN_counter = 0;
    LN_map = containers.Map();
    LN_LU_hist = containers.Map();
    
    % LU local_unlimited
    LU_ID = zeros(size(data,1),1);
    LU_counter = 0;
    LU_map = containers.Map();

    %
    fprintf('\n');
    fprintf('Predictions: [%d,%d] / %d\n',MIN,MAX, size(data,1));
    print_block = 0;
    
    for i=1:size(data,1)
        
        % prediction info
        % UID = i; % position in data array is UID
        %CYCLE = data(i,1);
        PC = data(i,2);
        %CONTEXT = data(i,3);
        %TARGET = data(i,4);
        BEHAVIOR = data(i,5);
        
        % SET ID %
        
        % ---- Local Limited ---- %
        
        str_pc = num2str( bitand(PC, bitshift(1,LOCAL_SIZE)-1 ));
        
        if( isKey( LL_hist ,str_pc ) )
            history = LL_hist( str_pc );
        else
            history = zeros(HISTORY_LENGTH,1);
        end
        
        bin_history = bi2de(history');
        
        uid = num2str( bitand(bitxor(bin_history,PC), bitshift(1,LOCAL_SIZE)-1 ) );
        [LL_counter LL_map LL_ID] = addOrSet( i , LL_map, uid, LL_ID, LL_counter );
        
        % update history
        history = circshift(history,1);
        history(1,1) = BEHAVIOR;
        LL_hist( str_pc ) = history;
        
        % ---------- %
        
        str_pc = num2str( PC );
        
        if( isKey( LN_LU_hist ,str_pc ) )
            history = LN_LU_hist( str_pc );
        else
            history = zeros(HISTORY_LENGTH,1);
        end
        bin_history = bi2de(history');
        str_history = num2str( bin_history );
        
        % LN
        uid = num2str( bitxor(bin_history,PC) );
        [LN_counter LN_map LN_ID] = addOrSet( i , LN_map, uid, LN_ID, LN_counter );
        
        % LU
        uid = strcat(str_history,'|',str_pc);
        [LU_counter LU_map LU_ID] = addOrSet( i , LU_map, uid, LU_ID, LU_counter );
        
        % update history
        history = circshift(history,1);
        history(1,1) = BEHAVIOR;
        LN_LU_hist( str_pc ) = history;
        
        % PRINT %
        
        if print_block == 0
            print_block = round(min( size(data,1)/10 , 2000 ));
            fprintf(' --- [%3.2f] (%d/%d) --- \n',i/size(data,1),MIN+i,MAX);
            fprintf('local_limit sets: %d\n',LL_counter);
            fprintf('local_nocol sets: %d\n',LN_counter);
            fprintf('local_unlim sets: %d\n',LU_counter);
        else
            print_block = print_block - 1;
        end
    end
    
    function check( ID , name )
        sets = unique( ID );
    
        % sanity check:
        accum = 0;
        for j=1:size(sets,1)
            count = size(find(ID == sets(j,1)),1);
            accum = accum + count;
        end
        assert( size(data,1) == accum );
        fprintf('Total: %s %4d / %4d predictions [%.3f].\n',name, size(sets,1),size(data,1),size(data,1)/size(sets,1));
    end

    fprintf('--- Results --- \n');
    check(LL_ID,'local_limit');
    check(LN_ID,'local_nocol');
    check(LU_ID,'local_unlim');
    
    % correlation LOCAL %
    
    fprintf(' ---- CORRELATION LOCAL ---- \n');
    
    % warning: these indexes are used to access 'matrix'
    LOCAL_LIMT = 1;
    LOCAL_NOCO = 2;
    LOCAL_UNLM = 3;
    
    LOCAL_LIMT_COLUMN = getIndex(file.textdata,'local_limited');
    LOCAL_NOCO_COLUMN = getIndex(file.textdata,'local_nocol');
    LOCAL_UNLM_COLUMN = getIndex(file.textdata,'local_unlimited');
    REAL_COLUMN = getIndex(file.textdata,'real');
    
    assert( LOCAL_LIMT_COLUMN ~= -1 );
    assert( LOCAL_NOCO_COLUMN ~= -1 );
    assert( LOCAL_UNLM_COLUMN ~= -1 );
    assert( REAL_COLUMN ~= -1 );
    
    % only analysis at most MAX predictions
    bests = zeros( size(data,1) , 1 );

    data_limt = data(:,LOCAL_LIMT_COLUMN);
    data_noco = data(:,LOCAL_NOCO_COLUMN);
    data_unlm = data(:,LOCAL_UNLM_COLUMN);
    data_real = data(:,REAL_COLUMN);
    
    limt_sets = unique( LL_ID ); % lower number , larger each
    noco_sets = unique( LN_ID );
    unlm_sets = unique( LU_ID ); % larger number , smaller each
    
    accum_count = 0;
    accum_limt = 0;
    accum_noco = 0;
    accum_unlm = 0;
    
    % for each small set
    for i=1:size(unlm_sets,1)
        % indexes for the members of this set
        indexes = find( LU_ID == unlm_sets(i,1) );
        
        filtered_real = data_real(indexes);
        
        miss_limt = sum( data_limt(indexes) ~= filtered_real );
        miss_noco = sum( data_noco(indexes) ~= filtered_real );
        miss_unlm = sum( data_unlm(indexes) ~= filtered_real );
        
        accum_limt = accum_limt + miss_limt;
        accum_noco = accum_noco + miss_noco;
        accum_unlm = accum_unlm + miss_unlm;
        
        % which one is the best?
        if( miss_limt <= miss_noco && miss_limt <= miss_unlm )
            bests( indexes ) = LOCAL_LIMT ;
            accum_count = accum_count + miss_limt;
            continue;
        end
        
        if( miss_noco < miss_limt && miss_noco <= miss_unlm )
            bests( indexes ) = LOCAL_NOCO ;
            accum_count = accum_count + miss_noco;
            continue;
        end
        
        if( miss_unlm < miss_limt && miss_unlm < miss_noco )
            bests( indexes ) = LOCAL_UNLM ;
            accum_count = accum_count + miss_unlm;
            continue;
        end
        
        % all cases should have been covered... very redundantly
        assert( false );
    end

    % do all predictions have a class?
    assert( size( bests( bests == 0 , : ) , 1 ) == 0 );
    
    % misses
    pred_total = size(data,1);
    accum_count = accum_count/pred_total*100;
    accum_limt = accum_limt/pred_total*100;
    accum_noco = accum_noco/pred_total*100;
    accum_unlm = accum_unlm/pred_total*100;
    
    fprintf('best: %.2f\n', accum_count );
    fprintf('base: %.2f (%.2f)\n', accum_limt, accum_limt-accum_count );
    fprintf('noco: %.2f (%.2f)\n', accum_noco, accum_noco-accum_count );
    fprintf('unlm: %.2f (%.2f)\n', accum_unlm, accum_unlm-accum_count );
    
    % 'bests' contains level where each single PREDICTION is best
    matrix = zeros( 3 , 3 );
    
    matrix(LOCAL_NOCO,LOCAL_LIMT) = NaN;
    matrix(LOCAL_UNLM,LOCAL_LIMT) = NaN;
    
    matrix(LOCAL_UNLM,LOCAL_NOCO) = NaN;

    % is LOCAL_LIMT best level ?
    for i=1:size( limt_sets, 1)
        indexes = find( LL_ID == limt_sets(i,1) );
        lvl = unique( bests(indexes) );
        if( size(lvl,1) == 1 && lvl(1,1) ~= -1 )
            % best 'prediction stream' is that of LOCAL_LIMT
            % best 'prediction set'
            matrix(LOCAL_LIMT,lvl(1,1)) = matrix(LOCAL_LIMT,lvl(1,1))+size(indexes,1);
            % mark as classified
            bests(indexes) = -1;
        end 
    end

    % is LOCAL_NOCO best level ?
    for i=1:size( noco_sets, 1)
        indexes = find( LN_ID == noco_sets(i,1) );
        lvl = unique( bests(indexes) );
        if( size(lvl,1) == 1 && lvl(1,1) ~= -1 )
            % best 'prediction stream' is that of LOCAL_NOCO
            % best 'prediction set'
            matrix(LOCAL_NOCO,lvl(1,1)) = matrix(LOCAL_NOCO,lvl(1,1))+size(indexes,1);
            % mark as classified
            bests(indexes) = -1;
        end
    end
    
    % is LOCAL_UNLM best level ?
    for i=1:size( unlm_sets, 1)
        indexes = find( LU_ID == unlm_sets(i,1) );
        lvl = unique( bests(indexes) );
        if( size(lvl,1) == 1 && lvl(1,1) ~= -1 )
            % best 'prediction stream' is that of GSHARE_NOCO
            % best 'prediction set'
            matrix(LOCAL_UNLM,lvl(1,1)) = matrix(LOCAL_UNLM,lvl(1,1))+size(indexes,1);
            % mark as classified
            bests(indexes) = -1;
        end
    end
    
    disp( matrix );
    disp( matrix/size(bests,1)*100 );
    
    %disp( sum(bests) );
    %disp( size(bests,1) );
    assert( sum(bests) == size(bests,1)*-1 );
   
    burstsAnalysis( limt_sets , LL_ID , data, data_limt, data_real , printer);
        
end

function correlationGSAHRE( file , MIN , MAX , printer )
    data = file.data;
    
    HISTORY_LENGTH = 32; % 32-bit history
    history = zeros(HISTORY_LENGTH,1);
    
    PATH_LENGTH = 32;
    path = zeros(PATH_LENGTH,1);
    
    % number of lines is dimension 1
    MAX = min( size(data,1) , MAX );
    MIN = min( MIN, MAX );
    MIN = max( 1 , MIN );
    
    data = data(MIN:MAX,:); % trim data
    
    % each prediction is marked with a set ID
    
    % GB gshare_base
    GSHARE_SIZE = 18;
    GB_ID = zeros(size(data,1),1);
    GB_counter = 0;
    GB_map = containers.Map();
    
    % GU gshare_unlimited
    GU_ID = zeros(size(data,1),1);
    GU_counter = 0;
    GU_map = containers.Map();
    
    % GN gshare_nocol
    GN_ID = zeros(size(data,1),1);
    GN_counter = 0;
    GN_map = containers.Map();
    
    % GP gshare_path
    GP_ID = zeros(size(data,1),1);
    GP_counter = 0;
    GP_map = containers.Map();

    %
    fprintf('\n');
    fprintf('Predictions: [%d,%d] / %d\n',MIN,MAX, size(data,1));
    print_block = 0;
    
    function [c MAP ID] = addOrSet( i, MAP , uid , ID , counter )
        c = counter;
        if( isKey( MAP ,uid) )
            ID(i,1) = MAP(uid);
        else
            c = c + 1;
            ID(i,1) = c;
            MAP(uid) = c;
        end
    end
    
    for i=1:size(data,1)
        
        % prediction info
        % UID = i; % position in data array is UID
        %CYCLE = data(i,1);
        PC = data(i,2);
        %CONTEXT = data(i,3);
        TARGET = data(i,4);
        BEHAVIOR = data(i,5);
        
        % SET ID %
        
        bin_history = bi2de(history');
        str_history = num2str(bin_history);
        str_path = path2str(path);
        str_pc = num2str(PC);
        
        % GB %
        
        uid = num2str( bitand(bitxor(bin_history,PC), bitshift(1,GSHARE_SIZE)-1 ) );
        [GB_counter GB_map GB_ID] = addOrSet( i , GB_map, uid, GB_ID, GB_counter );
        
        % GU %
        
        uid = num2str( bitxor(bin_history,PC) );
        [GU_counter GU_map GU_ID] = addOrSet( i , GU_map, uid, GU_ID, GU_counter );        
        
        % GN %
        
        uid = strcat(str_history,'|',str_pc);
        [GN_counter GN_map GN_ID] = addOrSet( i , GN_map, uid, GN_ID, GN_counter );
        
        % GP %
        
        uid = strcat(str_path,str_history,'|',str_pc);
        [GP_counter GP_map GP_ID] = addOrSet( i , GP_map, uid, GP_ID, GP_counter );

        % UPDATES %
        
        % update history
        history = circshift(history,1);
        % least significant bit is first
        history(1,1) = BEHAVIOR;
        
        % update path
        path = circshift(path,-1);
        path(PATH_LENGTH,1) = TARGET;

        % PRINT %
        
        if print_block == 0 
            print_block = round(min( size(data,1)/10 , 2000 ));
            fprintf(' --- [%3.2f] (%d/%d) --- \n',i/size(data,1),MIN+i,MAX);
            fprintf('gshare_base  sets: %d\n',GB_counter);
            fprintf('gshare_unlim sets: %d\n',GU_counter);
            fprintf('gshare_nocol sets: %d\n',GN_counter);
            fprintf('gshare_path  sets: %d\n',GP_counter);
        else
            print_block = print_block - 1;
        end
        
    end
    
    function check( ID , name )
        sets = unique( ID );
    
        % sanity check:
        accum = 0;
        for j=1:size(sets,1)
            count = size(find(ID == sets(j,1)),1);
            accum = accum + count;
        end
        assert( size(data,1) == accum );
        fprintf('Total: %s %4d / %4d predictions [%.3f].\n',name, size(sets,1),size(data,1),size(data,1)/size(sets,1));
    end

    fprintf('--- Results --- \n');
    check(GB_ID,'gshare_base ');
    check(GU_ID,'gshare_unlim');
    check(GN_ID,'gshare_nocol');
    check(GP_ID,'gshare_path ');
    
    % correlation GSAHRE %
    
    fprintf(' ---- CORRELATION GSHARE ---- \n');
    
    % warning: these indexes are used to access 'matrix'
    GSHARE_BASE = 1;
    GSHARE_UNLM = 2;
    GSHARE_NOCO = 3;
    GSHARE_PATH = 4;
    
    GSHARE_BASE_COLUMN = getIndex(file.textdata,'gshare_base');
    GSHARE_UNLM_COLUMN = getIndex(file.textdata,'gshare_unlimited');
    GSHARE_NOCO_COLUMN = getIndex(file.textdata,'gshare_nocol');
    GSHARE_PATH_COLUMN = getIndex(file.textdata,'gshare_path');
    REAL_COLUMN = getIndex(file.textdata,'real');
    
    assert( GSHARE_BASE_COLUMN ~= -1 );
    assert( GSHARE_UNLM_COLUMN ~= -1 );
    assert( GSHARE_NOCO_COLUMN ~= -1 );
    assert( GSHARE_PATH_COLUMN ~= -1 );
    assert( REAL_COLUMN ~= -1 );
    
    % only analysis at most MAX predictions
    bests = zeros( size(data,1) , 1 );

    data_base = data(:,GSHARE_BASE_COLUMN);
    data_unlm = data(:,GSHARE_UNLM_COLUMN);
    data_noco = data(:,GSHARE_NOCO_COLUMN);
    data_path = data(:,GSHARE_PATH_COLUMN);
    data_real = data(:,REAL_COLUMN);
    
    base_sets = unique( GB_ID ); % lower number , larger each
    unlm_sets = unique( GU_ID );
    noco_sets = unique( GN_ID );
    path_sets = unique( GP_ID ); % larger number , smaller each
    
    accum_count = 0;
    accum_base = 0;
    accum_unlm = 0;
    accum_noco = 0;
    accum_path = 0;
    
    % for each small set
    for i=1:size(path_sets,1)
        % indexes for the members of this set
        indexes = find( GP_ID == path_sets(i,1) );
        
        filtered_real = data_real(indexes);
        
        miss_base = sum( data_base(indexes) ~= filtered_real );
        miss_unlm = sum( data_unlm(indexes) ~= filtered_real );
        miss_noco = sum( data_noco(indexes) ~= filtered_real );
        miss_path = sum( data_path(indexes) ~= filtered_real );
        
        accum_base = accum_base + miss_base;
        accum_unlm = accum_unlm + miss_unlm;
        accum_noco = accum_noco + miss_noco;
        accum_path = accum_path + miss_path;
        
        % which one is the best?
        if( miss_base <= miss_unlm && miss_base <= miss_noco && miss_base <= miss_path )
            bests( indexes ) = GSHARE_BASE;
            accum_count = accum_count + miss_base;
            continue;
        end
        
        if( miss_unlm < miss_base && miss_unlm <= miss_noco && miss_unlm <= miss_path )
            bests( indexes ) = GSHARE_UNLM;
            accum_count = accum_count + miss_unlm;
            continue;
        end
        
        if( miss_noco < miss_base && miss_noco < miss_unlm && miss_noco <= miss_path )
            bests( indexes ) = GSHARE_NOCO;
            accum_count = accum_count + miss_noco;
            continue;
        end
        
        if( miss_path < miss_base && miss_path < miss_unlm && miss_path <= miss_noco )
            bests( indexes ) = GSHARE_PATH;
            accum_count = accum_count + miss_path;
            continue;
        end
        
        % all cases should have been covered... very redundantly
        assert( false );
    end
    
    % do all predictions have a class?
    assert( size( bests( bests == 0 , : ) , 1 ) == 0 );

    
    % misses
    pred_total = size(data,1);
    accum_count = accum_count/pred_total*100;
    accum_base = accum_base/pred_total*100;
    accum_noco = accum_noco/pred_total*100;
    accum_unlm = accum_unlm/pred_total*100;
    accum_path = accum_path/pred_total*100;
    
    fprintf('best: %.2f\n', accum_count );
    fprintf('base: %.2f (%.2f)\n', accum_base, accum_base-accum_count );
    fprintf('unlm: %.2f (%.2f)\n', accum_unlm, accum_unlm-accum_count );
    fprintf('noco: %.2f (%.2f)\n', accum_noco, accum_noco-accum_count );
    fprintf('path: %.2f (%.2f)\n', accum_path, accum_path-accum_count );
    
    % 'bests' contains level where each single PREDICTION is best
    matrix = zeros( 4 , 4 );
    
    matrix(GSHARE_UNLM,GSHARE_BASE) = NaN;
    matrix(GSHARE_NOCO,GSHARE_BASE) = NaN;
    matrix(GSHARE_PATH,GSHARE_BASE) = NaN;
    
    matrix(GSHARE_NOCO,GSHARE_UNLM) = NaN;
    matrix(GSHARE_PATH,GSHARE_UNLM) = NaN;
    
    matrix(GSHARE_PATH,GSHARE_NOCO) = NaN;

    % is GSHARE_BASE best level ?
    for i=1:size( base_sets, 1)
        indexes = find( GB_ID == base_sets(i,1) );
        lvl = unique( bests(indexes) );
        if( size(lvl,1) == 1 && lvl(1,1) ~= -1 )
            % best 'prediction stream' is that of GSHARE_BASE
            % best 'prediction set'
            matrix(GSHARE_BASE,lvl(1,1)) = matrix(GSHARE_BASE,lvl(1,1))+size(indexes,1);
            % mark as classified
            bests(indexes) = -1;
        end 
    end

    % is GSHARE_UNLM best level ?
    for i=1:size( unlm_sets, 1)
        indexes = find( GU_ID == unlm_sets(i,1) );
        lvl = unique( bests(indexes) );
        if( size(lvl,1) == 1 && lvl(1,1) ~= -1 )
            % best 'prediction stream' is that of GSHARE_UNLM
            % best 'prediction set'
            matrix(GSHARE_UNLM,lvl(1,1)) = matrix(GSHARE_UNLM,lvl(1,1))+size(indexes,1);
            % mark as classified
            bests(indexes) = -1;
        end
    end
    
    % is GSHARE_NOCO best level ?
    for i=1:size( noco_sets, 1)
        indexes = find( GN_ID == noco_sets(i,1) );
        lvl = unique( bests(indexes) );
        if( size(lvl,1) == 1 && lvl(1,1) ~= -1 )
            % best 'prediction stream' is that of GSHARE_NOCO
            % best 'prediction set'
            matrix(GSHARE_NOCO,lvl(1,1)) = matrix(GSHARE_NOCO,lvl(1,1))+size(indexes,1);
            % mark as classified
            bests(indexes) = -1;
        end
    end
    
    % is GSHARE_PATH best level ?
    for i=1:size( path_sets, 1)
        indexes = find( GP_ID == path_sets(i,1) );
        lvl = unique( bests(indexes) );
        if( size(lvl,1) == 1 && lvl(1,1) ~= -1 )
            % best 'prediction stream' is that of GSHARE_PATH
            % best 'prediction set'
            matrix(GSHARE_PATH,lvl(1,1)) = matrix(GSHARE_PATH,lvl(1,1))+size(indexes,1);
            % mark as classified
            bests(indexes) = -1;
        end
    end
    
    disp( matrix );
    disp( matrix/size(bests,1)*100 );
    
    %disp( sum(bests) );
    %disp( size(bests,1) );
    assert( sum(bests) == size(bests,1)*-1 );
   
    burstsAnalysis( base_sets , GB_ID , data, data_base, data_real , printer);
end

function burstsAnalysis( base_sets , map , data, data_pred, data_real, printer)
    base_misses = zeros( size(base_sets,1), 3 );
    
    for i=1:size( base_sets, 1)
        indexes = find( map == base_sets(i,1) );
        
        base_misses(i,1) = base_sets(i,1);
        base_misses(i,2) = size( indexes, 1 );
        base_misses(i,3) = sum( data_pred(indexes) ~= data_real(indexes) );
    end
    
    sorted = base_misses;
    sorted = sorted( sorted(:,2) > 1 , : ); % only for those sets larger that 1
    sorted = sortrows(sorted,-2); % sort by size, descending 
    
    filter_size = max( ceil(size(base_misses)/10) , 10 );
    % these are the biggest we are considering
    sorted = sorted(1:min(size(sorted,1),filter_size), : );
    sorted = sortrows(sorted,3); % sort by misses, ascending
    
    fprintf('BIG SETS: %d\n',size(sorted,1));
    
    bests = sorted(1:3,:);
    
    middle = round(size(sorted,1)/2);
    middle = max(1,middle-1);
    middle = sorted(middle:min(middle+3,size(sorted,1)),:);
    worsts = sorted(size(sorted,1)-2:end,:);
    
    fprintf('--- showing(bests): %d ---\n',size(bests,1));
    setPrinter(bests, map, data, data_real, printer);
    fprintf('===== END bests ====== \n');
    fprintf('--- showing(middle): %d ---\n',size(middle,1));
    setPrinter(middle, map, data, data_real, printer);
    fprintf('===== END middle ====== \n');
    fprintf('--- showing(worsts): %d ---\n',size(worsts,1));
    setPrinter(worsts, map, data, data_real, printer);
    fprintf('===== END worsts ====== \n');
end

% prints set characterization and its branches
function setPrinter( set , map , data_pred , data_real , printer )
    % for each branch in the set
    for i=1:size(set,1)
        fprintf('set #%d [size=%2d][miss=%.3f %d/%d]\n',set(i,1),set(i,2),set(i,3)/set(i,2),set(i,3),set(i,2));

        branch = set(i,1);
        % set's indexes in the trace
        indexes = find( map == branch );
        branches = data_real( indexes, :);
        [ warmup burst_number burts_flip transition_length taken nottaken] = setAnalysis( branches );

        fprintf('warm-up time: %d\n',warmup );

        bursts = burst_number( burst_number > -1 );
        fprintf('avg. stream burst: %2.3f\n',sum(bursts)/size(bursts,1));

        flips = burts_flip( burts_flip > -1 );
        fprintf('avg. burts flips : %2.3f\n',sum(flips)/size(flips,1));

        transitions = transition_length( transition_length > -1 );
        fprintf('avg. trans. leng.: %2.3f\n',sum(transitions)/size(transitions,1));

        fprintf('taken: %2d \t / not taken %2d\n',taken,nottaken);

        % prints sets characteristics
        fprintf('-- classification: --\n');
        printer( data_pred( indexes, : ) );
        fprintf('-----------\n');
    end
end

% burst analysis for a behavior, should only be used in a single set if it
% is used to yeal a set's burst analysis...
% use set's REAL branch behavior
% set should be of the form: [ 0 1 0 0 0 ... 1 ]' (n-rows,1-column)
function [ warmup burst_number burts_flip transition_length taken nottaken ] = ...
    setAnalysis( set_behavior )

    WARMUP_SUM = 3; % 2-bit counter only, (N-bit + 1)
    BURST_THRESHOLD = 2; % only a burst if at least 2

    warmup = -1;
    burst_number = -1;
    burts_flip = -1;
    transition_length = -1;

    w = 0;
    last = -1;
    count = 0;
    last_burst = -1;
    flips = 0;
    bursts = 0;
    n_bursts = 0;

    transition = 0;
    n_transition = 0;

    taken = 0;
    nottaken = 0;

    % the set is not significantly large
    if( size(set_behavior,1) < 2 )
        return;
    end

    for p=1:size(set_behavior,1)

        b = set_behavior(p,1);
        if( b == 0 )
            nottaken = nottaken + 1;
        else
            taken = taken+1;
        end

        % WARM UP %
        % only if not warmed up yet.
        if( abs(w) < WARMUP_SUM )
            % warm up : sum of taken/not taken is greater than N-bit +1
            if( b == 0 )
                w = w + -1;
            else
                w = w + 1;
            end
            if( abs(w) >= WARMUP_SUM )
                % ok, it has warmed...
                warmup = p;
            end
        end

        % BURST / TRANSITION %
        % last value forced to count as "break" to count lasts
        if( last == b && p~=size(set_behavior,1) )
            count = count+1;
        else
            if( last == -1 )
                count = 1;
            else
                if( last == b ) %p==size(set_behavior,1)
                    count = count+1;
                end

                if( count >= BURST_THRESHOLD )
                    bursts = bursts + count;
                    n_bursts = n_bursts + 1;
                    if( last_burst ~= -1 && last ~= last_burst )
                        flips = flips + 1;
                    end
                    last_burst = last;
                    n_transition = n_transition+1;
                else
                    transition = transition+1;

                    % if about to end the set, count this as a transition
                    if( p==size(set_behavior,1) )
                        n_transition = n_transition+1;
                    end
                end
                count = 0;
            end
            last = b;
        end
    end

    burst_number = bursts;%/size(set_behavior,1);
    burts_flip = flips; %/n_bursts;
    transition_length = transition; %/n_transition;
end

function str = path2str( path )
    str = '';
    for j=1:size(path,1)
        str = strcat(str,num2str(path(j,1)),'|');
    end
end

    
function printer = classify( file )

    % index of useful columns in 'file'
    TARGET_COLUMN = getIndex(file.textdata,'target');
    BRANCH_COLUMN = getIndex(file.textdata,'branch');
    REAL_COLUMN = getIndex(file.textdata,'real');
    
    assert( TARGET_COLUMN ~= -1 );
    assert( BRANCH_COLUMN ~= -1 );
    assert( REAL_COLUMN ~= -1 );
    
    % identify branches
    data = file.data;
    branches = unique(data(:,BRANCH_COLUMN));
    
    MAX_COMPLEX_SHIFTS = 32;
    
    % KINDS
    ALWAYS_KIND = 1;
    NEVER_KIND = 2;
    LOOP_KIND = 3;
    STRICT_KIND = 4;
    BLOCK_KIND = 5;
    COMPLEX_KIND = 6;
    SINGLE_TAKEN_KIND = 7;
    SINGLE_NOTTAKEN_KIND = 8;
    ALTERNATING = 9;
    OTHERS_KIND = 0; % default is others
            
    fprintf('-------- CLASSIFICATION -------- \n');
    
    fprintf('classifying: %d\n',size(branches,1));
    
    kinds = classification( branches );
    printKinds( kinds );
    
    printer = @(misses)printKinds(wrongs_classification( misses , kinds, branches ));
    
    function printKinds( kinds )
        
        one_tak = length( kinds( kinds == SINGLE_TAKEN_KIND , : ) );
        one_not = length( kinds( kinds == SINGLE_NOTTAKEN_KIND , : ) );
        always  = length( kinds( kinds == ALWAYS_KIND , : ) );
        never   = length( kinds( kinds == NEVER_KIND  , : ) );
        loop    = length( kinds( kinds == LOOP_KIND   , : ) );
        strict  = length( kinds( kinds == STRICT_KIND , : ) );
        block   = length( kinds( kinds == BLOCK_KIND  , : ) );
        pattern = length( kinds( kinds == COMPLEX_KIND , : ) );
        altern  = length( kinds( kinds == ALTERNATING , : ) );
        others  = length( kinds( kinds == OTHERS_KIND , : ) );
        total   = length( kinds );
        
        fprintf('one:\t\t%d\t%.2f\n', one_tak, one_tak/total*100 );
        fprintf('zero:\t\t%d\t%.2f\n', one_not, one_not/total*100 );
        fprintf('always:\t\t%d\t%.2f\n', always, always/total*100 );
        fprintf('never:\t\t%d\t%.2f\n', never, never/total*100 );
        fprintf('loop:\t\t%d\t%.2f\n', loop, loop/total*100 );
        fprintf('altern:\t\t%d\t%.2f\n', altern, altern/total*100 );
        fprintf('strict:\t\t%d\t%.2f\n', strict, strict/total*100 );
        fprintf('block:\t\t%d\t%.2f\n', block, block/total*100 );
        fprintf('complex:\t%d\t%.2f\n', pattern, pattern/total*100 );
        fprintf('others:\t\t%d\t%.2f\n', others, others/total*100 );
        fprintf('total=%d\n',total);
        
        assert( total == altern+one_tak+one_not+always+never+loop+strict+block+pattern+others);
    end

    % AUX FUNCTION DEFINITIONS %
    
    % how many times it missed on a specific class...
    function wrongs = wrongs_classification( misses , kinds, branches )
        wrongs = zeros( size(misses,1) , 1 );
        
        for i=1:size(misses,1)
            branch = misses(i,BRANCH_COLUMN);
            index = find( branches == branch );
            assert( size(index,1) == 1 );
            wrongs(i,1) = kinds(index,1);
        end

    end
    
    function kinds = classification( branches )
        kinds = zeros(size(branches,1),1);
        
        for i=1:size(branches,1)
            branch = branches(i,1);
            % fetch all rows with this branch
            % column 2 is 'branch' column
            branch_data = data( data(:,BRANCH_COLUMN) == branch , : );
            
            % SINGLE TAKEN / NOT %
            if( size(branch_data,1) == 1 )
                p = branch_data(:,REAL_COLUMN);
                if( p == 1 )
                    kinds(i,1) = SINGLE_TAKEN_KIND;
                    continue;
                else
                    kinds(i,1) = SINGLE_NOTTAKEN_KIND;
                    continue;
                end
            end
            
            % ALWAYS / NEVER %
            
            s = sum( branch_data(:,REAL_COLUMN) );
            if( s == 0 )
                % only contains 0s, thus "not taken"
                kinds(i,1) = NEVER_KIND;
                continue;
            end
            
            if( s == size(branch_data,1) )
                % same size as number of rows of data, thus "always taken"
                kinds(i,1) = ALWAYS_KIND;
                continue;
            end
            
            % LOOP %
            
            % they should all have the same target, thus only look at first
            if( branch_data(1,TARGET_COLUMN) < branch )
                % jump to a PC lower than branch's PC, thus "loop"
                kinds(i,1) = LOOP_KIND;
                continue;
            end
            
            % STRICT / BLOCK %
            
            nottaken = -1;
            taken = -1;
            
            n = 0;
            last = -1;
            sw = 0;
            
            strict_test = true;
            block_test = false;
            
            for j=1:size(branch_data,1)
                pred = branch_data(j,REAL_COLUMN);
                
                % on a value switch
                if( last ~= -1 && pred ~= last )
                    sw = sw + 1;
                    
                    % set initial values, if needed
                    if( taken == -1 && last == 1 )
                        taken = n;
                    end
                    if( nottaken == -1 && last == 0 )
                        nottaken = n;
                    end
                    
                    % if numbers don't match with previously observed
                    if( ( last == 1 && taken ~= n ) || ( last == 0 && nottaken ~= n ) )
                        
                        % not a strict block pattern
                        strict_test = false;
                        
                        % maybe the first block was cut?
                        % this is only valid if we are replacing with a larger
                        % block size, never smaller...
                        if( sw == 2 && ((last==1 && n>taken )||(last==0 && n>nottaken) ) )
                            block_test = true;
                            if( last == 1 )
                                taken = n;
                            else
                                nottaken = n;
                            end
                        else
                            % nope, not cut. just not a block
                            block_test = false;
                            break;
                        end
                    end
                    
                    % reset block counter
                    n = 0;
                end
                
                n = n+1;
                last = pred;
            end
            
            % remove those that break the limit eventhough they don't switch at
            % the end of their cycle
            if( strict_test )
                if( last == 0 )
                    if( nottaken == -1 )
                        nottaken = n;
                    else
                        if( n > nottaken )
                            strict_test = false;
                            
                            % maybe non-strict?
                            if( sw == 2 )
                                nottaken = n;
                                block_test = true;
                            else
                                block_test = false;
                            end
                        end
                    end
                else % last == 1
                    if( taken == -1 )
                        taken = n;
                    else
                        if( n > taken )
                            strict_test = false;
                            
                            % non-strict?
                            if( sw == 2 )
                                taken = n;
                                block_test = true;
                            else
                                block_test = false;
                            end
                        end
                    end
                end
            end
            
            if( strict_test )
                if( taken == 1 && nottaken == 1 )
                    kinds(i,1) = ALTERNATING;
                    continue;
                end
                kinds(i,1) = STRICT_KIND;
                continue;
            end
            if( block_test )
                kinds(i,1) = BLOCK_KIND;
                continue;
            end
            
            % COMPLEX %
            
            behavior = branch_data(:,REAL_COLUMN);
            max = size(behavior,1);
            
            complex = false;
            for j=1:min( max-1, MAX_COMPLEX_SHIFTS )
                shift = circshift(behavior,j);
                if( sum( xor(shift,behavior) ) == max )
                    complex = true;
                    break;
                end
            end
            if( complex )
                kinds(i,1) = COMPLEX_KIND;
                continue;
            end
            
        end
    end

end


% finds the column index that contains str
function res = getIndex(M,str)
    for i=1:length(M)
        if( strcmp( M(1,i) , str ) )
            res = i;
            return;
        end
    end
    res = -1;
end
